// 分治 - 归并
// 归并的核心思路就是先将数组分左右两块
// 再把左边数组排序，右边数组排序
// 再合并两个有序数组
// 类似于二叉树的后续遍历
// 典型的应用场景就是找逆序对 - 逆序对涉及到选择一左一右两个元素,这就是在合并两个有序数组涉及的操作,合并时统计逆序对数即可

// 例题 2：
// 在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。
// 请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
//
//        示例 1：
//
//        输入：record = [9, 7, 5, 4, 6]
//        输出：8
//        解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
//
//        提示：
//
//        0 <= record.length <= 50000

// 解题思路:
// 数组分左右两块 - 递归排序
// 合并两个有序数组 - 统计逆序对的个数
// 还原数组

public class ReversePairs {
    int ret = 0;
    public int reversePairs(int[] record) {
        int n = record.length;
        mergeSort(record, 0, n - 1);
        return ret;
    }
    public void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int l = left; int r = mid + 1;
        int n = right - left + 1;
        int[] tmp = new int[n];
        int cur = 0;
        while(l <= mid && r <= right){
            if(nums[l] <= nums[r]) tmp[cur++] = nums[l++];
            else{
                tmp[cur++] = nums[r++];
                ret += (mid - l + 1);
            }
        }
        while(l <= mid) tmp[cur++] = nums[l++];
        while(r <= right) tmp[cur++] = nums[r++];
        for(int i = 0; i < n; i++) nums[i + left] = tmp[i];
    }
}
